/*
    什么是滑动窗口：利用单调性的“同向双指针”, 优化暴力枚举
    利用单调性，规避很多没必要的枚举
    时间复杂度：O(N^2)
    大致过程：进窗口 -> 判断 -> 出窗口
*/

// 209. 长度最小的子数组
// class Solution {
// public:
//     int minSubArrayLen(int target, vector<int>& nums) {
//         int n = nums.size();
//         int left = 0, right = 0, sum = nums[0];
//         int minL = INT_MAX;
//         while(right < n)
//         {
//             if(sum < target)
//             {
//                 right++;
//                 if(right < n) sum += nums[right];
//             }
//             else
//             {
//                 //sum >= target
//                 minL = min(minL, right - left + 1);

//                 //sum减少(left++)可能满足条件，sum增大(right++)必然满足条件
//                 //但是right++后，子数组长度变长，没必要再探测了
//                 //所以此时只让left++，先让子数组长度变短，再判断是否满足条件
//                 sum -= nums[left++];
//             }
//         }

//         return minL == INT_MAX ? 0 :minL;
//     }
// };

// 3. 无复字符的最长子串
// class Solution {
// public:
//     int lengthOfLongestSubstring(string s) {
//         // // 1.pos[i]记录元素i在s中的位置, pos[i]=-1代表元素i在s中未出现
//         // int pos[128];
//         // for(int i = 0; i < 128 ; i++) pos[i] = -1;

//         // // 2.
//         // int maxLen = 0;
//         // for(int left = 0, right = 0 ; right < n ; right++)
//         // {   
//         //     if(pos[s[right]] >= 0)
//         //     {
//         //         // s[right]在前面的子串中存在
//         //         // left --> pos[s[right]] + 1;
//         //         // 使pos数组始终维护的是s[left, right-1]范围内的元素位置
//         //         while(left <= pos[s[right]]) pos[s[left++]] = -1;
//         //     }
//         //     pos[s[right]] = right;
//         //     maxLen = max(maxLen, right - left + 1);
//         // }
//         // return maxLen;

//         int hash[128] = {0};//存储元素出现的次数
//         int maxLen = 0, n = s.size();
//         for(int left = 0, right = 0; right < n ; right++)
//         {
//             //出现重复元素
//             while(hash[s[right]] > 0)
//             {
//                 //出窗口
//                 hash[s[left++]]--;
//             }
//             //进窗口
//             hash[s[right]]++;
//             //计算结果
//             maxLen = max(maxLen, right - left + 1);
//         }
//         return maxLen;
//     }
// };

// 1004. 最大连续1的个数 III
// class Solution {
// public:
//     int longestOnes(vector<int>& nums, int k) {
//         int n = nums.size();
//         int left = 0, right = 0, ret = 0, curZeroCnt = 0;
//         while(right < n)
//         {
//             if(nums[right] == 0)
//             {
//                 if(curZeroCnt+1 <= k) curZeroCnt++;
//                 else
//                 {
//                     //计算结果
//                     ret = max(ret, right - left);
//                     //left越过一个0为止（出窗口）
//                     while(nums[left++] != 0);
//                 }
//             }
//             //入窗口
//             right++;
//         }
//         ret = max(ret, right - left);
//         return ret;
//     }
// };

//1658.
// class Solution {
// public:
//     int minOperations(vector<int>& nums, int x) {
//         int n = nums.size();
//         //1.求数组nums的总和sum
//         int sum = 0;
//         for(auto e : nums) sum += e;
//         if(sum < x) return -1;

//         //2.求和为sum-x的最长子数组(滑动窗口)
//         int curSum = 0, maxLen = -1;
//         for(int left = 0, right = 0; right < n ; right++)
//         {
//             curSum += nums[right];//进窗口
//             while(curSum > sum - x)
//                 curSum -= nums[left++];//出窗口
//             if(curSum == sum - x)
//                 maxLen = max(maxLen, right - left + 1);
//         }   

//         //3.将x减到0的最小操作数 == 和为x的最小数组长度 == 总长度 - 和为sum-x的最长数组长度
//         return  maxLen == -1 ? maxLen : n - maxLen;
//     }
// };

// 438.
// class Solution {
// public:
//     vector<int> findAnagrams(string s, string p) {
//         //1.创建两个哈希表
//         int shash[26] = {0}, phash[26] = {0};
//         for(auto& ch : p) phash[ch - 'a']++;

//         //2.
//         vector<int> ret;
//         int left = 0, right = 0;
//         while(right < s.size())
//         {
//             if(phash[s[right] - 'a'])
//             {
//                 //right指向字母在p字符串中
//                 shash[s[right] - 'a']++;
//                 //如果s[left, right]中出现字母个数大于p，要减少到和p一样为止
//                 while(shash[s[right] - 'a'] > phash[s[right] - 'a']) 
//                     shash[s[left++] - 'a']--;
//             }
//             else
//             {
//                 //right指向字母不在p字符串中
//                 //先让left走到right后一位为了更新shash, 后一位是因为以right开头的子串必无效
//                 while(left < right)
//                 {
//                     if(shash[s[left] - 'a'] > 0)
//                         shash[s[left++] - 'a']--;
//                 }
//                 left++;
//             }
//             right++;

//             if(right - left == p.size()) ret.push_back(left);
//         }
//         return ret;
//     }
// };

//30.438题的变体
// class Solution {
// public:
//     vector<int> findSubstring(string s, vector<string>& words) {
//         // 1.hash1记录words中每个字符串出现的次数
//         vector<int> ret;
//         unordered_map<string, int> hash1;
//         for(auto& w : words) hash1[w]++;    

//         // 2.滑动窗口
//         int len = words[0].size();//单个word的长度->指针移动的步长
//         unordered_map<string, int> hash2;//记录s窗口中字符串出现次数

//         for(int begin = 0; begin < len; begin++)//, 以不同位置起始,将每个字符串看作一个整体
//         {
//             //清理hash2, 每一趟滑动用一个hash2
//             hash2.clear();
//             int count = 0;//统计有效字符串个数
//             for(int left = begin, right = left; right + len <= s.size(); right += len)
//             {
//                 string rstr = s.substr(right, len);//right指向的字符串 
//                 hash2[rstr]++;//入窗口
//                 if(hash1.count(rstr) && hash2[rstr] <= hash1[rstr])//维护count
//                     count++;//有效字符串
                
//                 if((right - left)/len + 1 > words.size())
//                 {
//                     string lstr = s.substr(left, len);//left指向的字符串
//                     if(hash1.count(lstr) && hash2[lstr] <= hash1[lstr])//维护count
//                         count--;//有效字符串

//                     hash2[lstr]--;//出窗口
//                     left += len;
//                 }
//                 if(count == words.size())//此时，[left, right]中字符串个数<=words.size
//                     ret.push_back(left);
//             }
//         }
//         return ret;
//     }
// };

//76
// class Solution {
// public:
    // bool check(string t)
    // {
    //     for(auto& ch : t)
    //     {
    //         if(hash2[ch] < hash1[ch]) return false;
    //     }
    //     return true;
    // }
//     string minWindow(string s, string t) {
//         int hash1[128] ={0}, hash2[128] = {0};
//         int kinds = 0;//有效字符的种类
//         for(auto& ch : t) 
//             if(++hash1[ch] == 1) kinds++;

//         int begin = 0, minLen = INT_MAX;
//         int count = 0;//统计有效字符的种类数目
//         for(int left = 0, right = 0; right < s.size(); right++)
//         {
//             //入窗口    
//             if(++hash2[s[right]] == hash1[s[right]])
//                 count++;

//             while(count == kinds)
//             {
//                 //1.保存结果
//                 if(right - left + 1 < minLen) 
//                 {
//                     begin = left;
//                     minLen = right-left+1;
//                 }
//                 //2.出窗口
//                 if(hash2[s[left]]-- == hash1[s[left]])
//                     count--;
//                 left++;
//             }
//         }
//         return minLen == INT_MAX ? "" : s.substr(begin, minLen);
//     }
// };